//
// Description: 376. 摆动序列
// Created by Loading on 2022/7/10.
//

#include <bits/stdc++.h>

using namespace std;

int wiggleMaxLength(vector<int> &nums) {
    int n = nums.size();
    if (n < 2) {
        return n;
    }

    // up[i] 表示前 i 位置所有元素，且最后是摆动上升的最长摆动子序列长度
    // down[i] 表示前 i 位置所有元素，且最后是摆动下降的最长摆动子序列长度
    vector<int> up(n), down(n);
    up[0] = down[0] = 1;
    for (int i = 1; i < n; ++i) {
        if (nums[i] < nums[i - 1]) {
            // 下降，摆动上升序列忽略，摆动下降序列由两个序列的 i - 1 位置更新
            up[i] = up[i - 1];
            down[i] = max(up[i - 1] + 1, down[i - 1]);
        } else if (nums[i] > nums[i - 1]) {
            // 上升，摆动下降序列忽略，摆动上升序列由两个序列的 i - 1 位置更新
            up[i] = max(down[i - 1] + 1, up[i - 1]);
            down[i] = down[i - 1];
        } else {
            // 相等，忽略
            up[i] = up[i - 1];
            down[i] = down[i - 1];
        }
    }

    return max(up[n - 1], down[n - 1]);
}

int main() {
    vector<int> nums{1, 7, 4, 9, 2, 5};

    int res = wiggleMaxLength(nums);

    cout << res << endl;

    return 0;
}
